//https://leetcode.cn/problems/beautiful-towers-ii/


class Solution {
public:
    long long maximumSumOfHeights(vector<int>& maxHeights) {
        //单调栈并记录
        int n=maxHeights.size();
        vector<long long> left(n),right(n);
        vector<int> s;
        s.push_back(-1);
        //左遍历单调
        for(int i=0;i<n;++i){
            while(s.back()!=-1&&maxHeights[s.back()]>maxHeights[i]){
                s.pop_back();
            }
            long long sum=(long long)maxHeights[i]*(i-s.back());
            if(s.back()!=-1) sum+=left[s.back()];
            left[i]=sum;
            s.push_back(i);
        }
        //右遍历单调
        s.clear();
        s.push_back(n);
        for(int i=n-1;i>=0;--i){
            while(s.back()!=n&&maxHeights[s.back()]>maxHeights[i]){
                s.pop_back();
            }
            long long sum=(long long)maxHeights[i]*(s.back()-i);
            if(s.back()!=n) sum+=right[s.back()];
            right[i]=sum;
            s.push_back(i);
        }
        long long ans=0;
        for(int i=0;i<n;++i){
            ans=max(ans,right[i]+left[i]-maxHeights[i]);
        }
        return ans;
    }
};




